NOIP2006 普及组

Actinoi 7月 21, 2019

T1:明明的随机数

题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了个到之间的随机整数，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

输入输出格式

输入格式：

输入有两行，第行为个正整数，表示所生成的随机数的个数

第行有个用空格隔开的正整数，为所产生的随机数。

输出格式：

输出也是两行，第行为个正整数，表示不相同的随机数的个数。

第行为个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

输入输出样例

输入样例#1：

10
20 40 32 67 40 20 89 300 400 15

输出样例#1：

8
15 20 32 40 67 89 300 400

说明

NOIP 2006 普及组第一题

题解：

考虑到每个数字最大只有，我们便可以设置一个数组，每读入一个数字后，所对应的数组中的位置便加，最后，对数组从至进行枚举，如果枚举到的数字不是的话，就输出这个序号。

#include <iostream>
using namespace std;
int t[1001]; //存储数字
int main() {
    int n; //表示所生成的随机数的个数
    cin >> n;
    int number = 0; //临时变量number
    int sum = 0; //表示不相同的随机数的个数
    for (int i = 1; i <= n; i++) {
        cin >> number;
        t[number]++;
        if (t[number] == 1) //第一次存入，一个新的随机数
            sum++;
    }
    cout << sum << endl;
    for (int i = 1; i <= 1000; i++)
        if (t[i] != 0)
            cout << i << " ";
    return 0;
}

T2:开心的金明

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的元。于是，他把每件物品规定了一个重要度，分为等：用整数表示，第等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过元（可以等于元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第件物品的价格为，重要度为，共选中了件物品，编号依次为，则所求的总和为：

。

请你帮助金明设计一个满足要求的购物单。

输入输出格式

输入格式：

第一行，为个正整数，用一个空格隔开：（其中表示总钱数，为希望购买物品的个数。）

从第行到第行，第行给出了编号为的物品的基本数据，每行有个非负整数（其中表示该物品的价格，表示该物品的重要度()

输出格式：

个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值。

输入输出样例

输入样例#1：

输出样例#1：

说明

NOIP 2006 普及组第二题

题解：

本题为一道经典的背包问题，我们枚举每件物品，以剩余的钱数为单位进行枚举，很容易得到的状态转移方程。

#include <iostream>
using namespace std;
int things[26][4];
int DP[30001]; //每个钱最多能买多少东西
int main() {
    int N, m;
    cin >> N >> m;
    for (int i = 1; i <= m; i++){
        cin >> things[i][1] >> things[i][2];
        things[i][3] = things[i][1] * things[i][2]; //物品的价格与重要度乘积
    }
    for (int i = 1; i <= m; i++)
        for (int j = N; j >= 1; j--)
            if (j - things[i][1] >= 0)
                DP[j] = max(DP[j - things[i][1]] + things[i][3], DP[j]);
    cout << DP[N];
    return 0;
}

T3:Jam的计数法

题目描述

是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。

在他的计数法中，每个数字的位数都是相同的（使用相同个数的字母），英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。我们把这样的“数字”称为数字。在数字中，每个字母互不相同，而且从左到右是严格递增的。每次，还指定使用字母的范围，例如，从到，表示只能使用这些字母。如果再规定位数为，那么，紧接在数字“”之后的数字应该是“”。（如果我们用、依次表示数字“”与“”，则，且不存在数字，使）。

你的任务是：对于从文件读入的一个数字，按顺序输出紧接在后面的个数字，如果后面没有那么多数字，那么有几个就输出几个。

输入输出格式

输入格式：

共行。

第行为个正整数，用一个空格隔开：（其中为所使用的最小的字母的序号，为所使用的最大的字母的序号。为数字的位数，这个数满足：）

第行为具有个小写字母的字符串，为一个符合要求的数字。

所给的数据都是正确的，不必验证。

输出格式：

最多为行，为紧接在输入的数字后面的个数字，如果后面没有那么多数字，那么有几个就输出几个。每行只输出一个数字，是由个小写字母组成的字符串，不要有多余的空格。

输入输出样例

输入样例#1：

2 10 5
bdfij

输出样例#1：

bdghi
bdghj
bdgij
bdhij
befgh

说明

NOIP 2006 普及组第三题

题解：

读完题目之后，我们可以想，什么时候这个数字最小呢？无疑，如果最后一位数字能够加的话，那么我们新得到的数字绝对是最小的。但是，如果最后一位加大于怎么办呢？这个时候怎样构建数字最小呢？我们便可以向前一位寻找，如果倒数第二位一位加不大于的话，我们便更新倒数第二位的数字。由于数字是左到右是严格递增的，所以我们便向后更新，为了确保得到的数字尽可能地小，当前位数上的数字也就是上一位上的数字加，这样，我们便可以令数字最小了。

整理一下上面的思路，也就是从最后一位数字开始枚举，如果它加不大于的话，我们便更新这个数字。否则，便向前一位寻找有没有数字可以更新，如果有的话，便更新这个数字。为了确保数字值最小且满足左到右是严格递增的要求，我们将它后面的数字依次更新，使得这个数字后面的所有数字都是前面数字的值加。如果找到了第一位且无法更新的话，那么便停止计算。

还不太明白的同学可以看一下代码：

#include <iostream>
using namespace std;
int main() {
    int s, t, w; //s为所使用的最小的字母的序号，t为所使用的最大的字母的序号，w为数字的位数
    string Jam;
    cin >> s >> t >> w >> Jam;
    bool r = false; //判断是否更新了Jam数字
    int k = 0;
    for (int q = 1; q <= 5; q++) { //输出5个Jam数字
        for (int i = w - 1; i >= 0; i--) { //从最后一位开始，向前查找能不能替换
            if (Jam[i] + 1 <= 'a' - 1 + t - k) { //如果加一不超过最大值，则更新
                Jam[i] = Jam[i] + 1;
                for (int j = i + 1; j <= w; j++)
                    Jam[j] = Jam[j - 1] + 1;
                r = true;
                break;
            }
            k++;
        }
        if (r == true) //判断是否更新了Jam数字
            cout << Jam << endl; //输出当前的Jam数字
        else
            return 0;
        k = 0;
        r = false;
    }
    return 0;
}

T4:数列

题目描述

给定一个正整数,把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当时时，这个序列是：

（该序列实际上就是：）

请你求出这个序列的第项的值（用进制数表示）。

例如，对于，，正确答案应该是。

输入输出格式

输入格式：

个正整数，用一个空格隔开：

（、的含义与上述的问题描述一致，且）。

输出格式：

个正整数。（整数前不要有空格和其他符号）。

输入输出样例

输入样例#1：

3 100

输出样例#1：

说明

NOIP 2006 普及组第四题

题解：

读过题目之后，（一头雾水），有啥方法可以解决这道题呢？无疑，我们会想到暴力。。。但是暴力的话会。那应该怎么办呢？

再仔细读一遍题，题目中有一句“用进制数表示”的话。这句话可不常见，莫非。。。它在提示我们这个题与进制有关？

我们将这个数列分解成三进制，便可以得到：

它长得好像一个二进制数列w！（小声嘀咕

那么，如果把这个三进制数列当成二进制数列，转成十进制是多少呢？

发现规律了吧！

所以，我们便可以将十进制数字先转成二进制数字，然后再把二进制数字当作进制数字，再转成十进制，便得到我们的答案辣！

#include <cmath>
#include <iostream>
using namespace std;
long long a[100001];
int main() {
    long long k, n;
    cin >> k >> n;
    //将n转位二进制
    long long i = 1;
    while (n) {
        a[i++] = n % 2;
        n /= 2;
    }
    //将这个二进制数字当作k进制，再转到十进制
    long long q = i - 2, ans = 0;
    for (long long j = i - 1; j >= 1; j--) {
        ans += a[j] * pow(k, q);
        q--;
    }
    cout << ans << endl;
    return 0;
}